# 14. 加油站.py
import math
from typing import List

# 这种方法是以一种启发式的思路来寻找贪心点，答案并不完备。
class Part_Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        diff = list()
        max_diff = -math.inf
        ans = -1
        # 贪心法寻找初始点(不完备)
        for i in range(length):
            gas_diff = gas[i] - cost[i]
            if gas_diff > max_diff:
                max_diff = gas_diff
                # 油箱差值要比0大才能确保出发
                if max_diff > 0:
                    ans = i
            diff.append(gas_diff)
        # 模拟判断是否能够走完全程
        if ans == -1:
            return ans
        current_gas = gas[ans]
        next_cost = cost[ans]
        for j in range(1, length+1):
            if current_gas < next_cost:
                return -1
            else:
                next_index = (ans + j) % length
                current_gas = current_gas - next_cost + gas[next_index]
                next_cost = cost[next_index]
        return ans

# 蛮力法：会超时。
class Brute_Force_Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        # 默认不可行
        available = False
        for i in range(length):
            ans = i
            # 依次判断当前的初始点是否可行
            current_gas = gas[ans]
            next_cost = cost[ans]
            for j in range(1, length + 1):
                if current_gas < next_cost:
                    # 代表当前的初始点不可行
                    available = False
                    break
                else:
                    next_index = (ans + j) % length
                    current_gas = current_gas - next_cost + gas[next_index]
                    next_cost = cost[next_index]
                    available = True
            # 找到可行则直接返回
            if available:
                return ans
            else:
                ans = -1
        return -1

# 官方题解：是进行不等式的优化，对我来说，并不是很好理解和思考到，这是对蛮力法的优化。
# 由不等式可以证得：如果从x出发无法抵达y的下一个位置，但是可以抵达x到y包括y在内的任何一个位置，
# 那么即使从x到y中（包含x和y）的任何一个位置出发的话，也是无法到达y的下一个位置的，所以这些位置就无需查看了。
# 那么就只需要先从第0个位置开始验证，如果出现不可达的位置的话，那就以这个位置为起始点继续验证，
# 直到所有的点都验证完毕，或者找到可行解。
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        length = len(gas)
        ans = 0
        while ans < length:
            sum_of_gas = sum_of_cost = 0
            cnt = 0
            while cnt < length:
                index = (ans + cnt) % length
                sum_of_gas += gas[index]
                sum_of_cost += cost[index]
                if sum_of_gas < sum_of_cost:
                    break
                cnt += 1
            if cnt == length:
                return ans
            else:
                ans = ans + cnt + 1
        return -1